import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-08-29
 * Time: 15:02
 *
 */
public class Sort {
    //1.直接插入排序
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j=i-1;
            for (;j >= 0 ; j--) {
                if(array[j] > tmp){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            //每次如果都没有走到break那一步时，j都是会被减到-1的，并且tmp的值都没有被重新放到数组中
            array[j+1]=tmp;
        }
    }

    public static void shellSort(int[] array){
        int gap= array.length;
        while(gap > 1){
            gap=gap/2;
            shell(array,gap);
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j=i-gap;
            for(;j >= 0;j -= gap){
                if(array[j] > tmp){
                    array[j+gap]=array[j];
                }else {
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public static void selectSort2(int[] array){
        int left=0;
        int right=array.length-1;
        for (int i = left; i < right ; i++) {
            int minIndex=i;
            int maxIndex=i;
            for (int j = i+1; j <= right ; j++) {
                if(array[j] < array[minIndex]){
                    minIndex=j;
                }
                if(array[j] > array[maxIndex]){
                    maxIndex=j;
                }
            }
            swap(array,left,minIndex);
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }


    //从小到大的堆排序，建立大根堆
    public static void siftDown(int[] array,int parent,int end){
        int child=2*parent+1;
        while(child < end){
            if(child+1 < end && array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else {
                break;
            }
        }
    }

    public static void createHeap(int[] array){
        int parent= (array.length-1-1)/2;
        for (int i = parent ; i >=0 ; i--) {
            siftDown(array,parent, array.length);
        }
    }

    public static void heapSort(int[] array){
        int end=array.length-1;
        createHeap(array);
        while(end>0) {
            swap(array, 0, end);
            siftDown(array, 0, end);
            end--;
        }
    }

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1 ; i++) {//表示比较的总趟数
            boolean isChange=false;
            for (int j = 0; j < array.length-i-1 ; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    isChange=true;
                }
            }
            if(!isChange){
                break;
            }
        }
    }


    public static void quick(int[] array){
        quickSort(array,0, array.length-1);
    }
    public static void quickSort(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        int pivot=partitionHoare(array,start,end);
        //int pivot=partitionDig(array,start,end);
        quickSort(array,start,pivot-1);
        quickSort(array,pivot+1,end);

    }

    public static int partitionHoare(int[] array,int left,int right){
        int tmp=array[left];
        int index=left;
        while(left < right){
            while (left < right && array[right] >= tmp){
                right--;
            }
            while(left < right && array[left] <= tmp){
                left--;
            }
            swap(array,left,right);
        }
        swap(array,left,index);

        return right;
    }

    public static int partitionDig(int[] array,int left,int right){
        int key=array[left];
        while(left < right){
            while(left < right && array[right] >= key){
                right--;
            }
            array[left]=array[right];
            while(left < right && array[left] <= key){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=key;
        return left;
    }

    public static void partitionPoint(int[] array,int left,int right){
        int key=array[left];
        int cur=left+1;
        int prev=left;
        while(cur <= right){
            if(array[cur] < key && array[++prev]!=array[cur]){//prev下标一直在小于基准的最后一个下标处
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
    }

    //快速排序优化
    //三数取中法
    //递归到小的子区间时，可以考虑使用插入排序
    public static void quickSortPlus(int[] array,int start,int end){
        if(start >= end){
            return;
        }

        if(end-start+1 < 4){
            insertSortRange(array,start,end);
            return;
        }

        int middle=getMiddleNum(array,start,end);
        swap(array,start,middle);
        //让middle成为基准

        int pivot=partitionHoare(array,start,end);
        //int pivot=partitionDig(array,start,end);
        quickSortPlus(array,start,pivot-1);
        quickSortPlus(array,pivot+1,end);
    }

    public static int getMiddleNum(int[] array,int left,int right){
        int middle=(left+right)/2;
        if(array[left] < array[right]){
            if(array[middle] > array[right]){
                return right;
            }else if(array[middle] < array[right]){
                return left;
            }else {
                return middle;
            }
        }else {
            if(array[middle] > array[left]){
                return left;
            }else if(array[middle] < array[right]){
                return right;
            }else {
                return middle;
            }
        }
    }

    public static void insertSortRange(int[] array,int left,int right){
        for (int i=left+1; i <= right ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >= left; j--) {
                if(array[j] > tmp){
                    array[j+1]=array[j];
                }else {
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    public static void quickSortNor(int[] array,int start,int end){
        int pivot=partitionHoare(array,start,end);
        Stack<Integer> stack=new Stack<>();
        //Deque<Integer> stack2=new ArrayDeque<>();
        if(pivot < start+1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if(pivot > end-1){
            stack.push(pivot+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end=stack.pop();
            start=stack.pop();
            pivot=partitionHoare(array,start,end);
            if(pivot < start+1) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if(pivot > end-1){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

    public static void mergeSort(int[] array){
        int start=0;
        int end= array.length-1;
        mergeTmp(array,start,end);
    }

    private static void mergeTmp(int[] array, int left, int right) {
        if(left >= right){//正常情况下只会出现left==right，写left>right只是为了防止使用者输入错误
            return;
        }
        int mid=(left+right)/2;
        mergeTmp(array,left,mid);
        mergeTmp(array,mid+1,right);
        //到这一步已经把最左边的两个分成单个的
        //并且这一步是到那个两个两个为一组的那层，并且merge方法里面的left，mid，right，就是两个为一组的left,right,mid
        //现在要合并
        merge(array,left,mid,right);//合并两个有序数组的操作
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp=new int[right-left+1];
        int s1=left;
        //int e1=mid;
        int s2=mid+1;
        //int e2=right;
        int index=0;

        while(s1 <= mid && s2 <= right){
            if(array[s1] <= array[s2]){
                tmp[index]=array[s1];
                index++;
                s1++;
            }else{
                tmp[index]=array[s2];
                index++;
                s2++;
            }
        }

        while(s1 <= mid){
            tmp[index]=array[s1];
            index++;
            s1++;
        }
        while(s2 <= right){
            tmp[index]=array[s2];
            index++;
            s2++;
        }

        for (int i = 0; i < index; i++) {//我们的目的是在原数组array上面修改，所以要把tmp数组里面的值给到array
            array[i+left]=tmp[i];//要知道不是每次遍历array都是从下标0开始的，应该要加上一个left
        }
    }

    public static void mergeSortNor(int[] array){
        int gap=1;
        while(gap < array.length){
            for (int i = 0; i < array.length; i=i+2*gap) {
                int left=i;
                int mid=left+gap-1;
                if(mid >= array.length){
                    mid=array.length-1;
                }
                int right=mid+gap;
                if(right >= array.length){
                    right= array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
}


